#include<vector>
#include<iostream>
#include<numeric>
#include<functional>
#include<algorithm>
#include<queue>
using namespace std;

namespace leetcode{
    class solution_207_zkm{
    /*
    @name:   课程表，判断当前的排课是否合理
    @url:    https://leetcode-cn.com/problems/course-schedule/
    @method: 拓扑排序
    */
    public:
        solution_207_zkm(){
            vector<vector<int>>courses;
            int n;
            get_data(courses,n);
            cout<<canFinish(n,courses)<<endl;
        }

        void get_data(vector<vector<int>>& data, int &n){
            n = 2;
            data = {{1,0},{0,1}};
        }
        void get_data(vector<vector<int>>& data, int &n){
            data = {{1,0}};
            n = 2;
        }

        bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
            if(prerequisites.size()<2)return true;
            vector<vector<int>> Edges(numCourses);
            vector<int> inDegrees(numCourses, 0);
            for(vector<int>& e:prerequisites){
                Edges[e[1]].push_back(e[0]);
                inDegrees[e[0]]++;
            }
            queue<int> q;
            for(int i=numCourses-1;i>=0;--i){
                if(inDegrees[i]==0){
                    q.push(i);
                    --numCourses;
                }
            }
            while(!q.empty()){
                int f = q.front();q.pop();
                for(int i:Edges[f]){
                    --inDegrees[i];
                    if(inDegrees[i]==0){
                        q.push(i);
                        --numCourses;
                    }
                }
            }
            return numCourses==0;
        }

    };

    class solution_210_zkm{
    /*
    @name:   课程表2, 返回课程的上课顺序。
    @url:    https://leetcode-cn.com/problems/course-schedule-ii/
    @method: 拓扑排序
    */
    public:
        solution_210_zkm(){
            vector<vector<int>> data;
            int n;
        }


        vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites){
            vector<int> ans(numCourses);
            vector<int> inDegrees(numCourses,0);
            vector<vector<int>> graph(numCourses);
            for(auto p:prerequisites){
                ++inDegrees[p[0]];
                graph[p[1]].push_back(p[0]);
            }
            queue<int> q;
            for(int i=0;i<numCourses;++i){
                if(inDegrees[i]==0)q.push(i);
            }
            int cnt = 0;
            while(!q.empty()){
                int f = q.front();q.pop();
                ans[cnt] = f;
                ++cnt;
                for(int i:graph[f]){
                    --inDegrees[i];
                    if(inDegrees[i]==0)q.push(i);
                }
            }
            return cnt==numCourses?ans:vector<int>();
        }
    };


    class solution_630_zkm{
    /*
    @name:   课程表3, 返回可以最多修读的课程数目
    @url:    https://leetcode-cn.com/problems/course-schedule-iii/
    @method: 优先队列，尽可能去修完时间靠前的课程。
    */
    public:
        solution_630_zkm(){}

        int scheduleCourse(vector<vector<int>>& courses) {
            sort(courses.begin(), courses.end(), [](const auto& c0, const auto& c1) {
                return c0[1] < c1[1];
            });

            priority_queue<int> q;
            // 优先队列中所有课程的总时间
            int total = 0;

            for (const auto& course: courses) {
                int ti = course[0], di = course[1];
                if (total + ti <= di) {
                    total += ti;
                    q.push(ti);
                }
                else if (!q.empty() && q.top() > ti) {
                    total -= q.top() - ti;
                    q.pop();
                    q.push(ti);
                }
            }

            return q.size();
    }
    };


    class solution_1462_zkm{
    /*
    @name:   课程表4, 返回查询的两者之间是否存在前置课程条件
    @url:    https://leetcode-cn.com/problems/course-schedule-iv/
    @method: floyd算法
    */
    public:
        solution_1462_zkm(){}

        vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
            vector<vector<bool> > graph(numCourses, vector<bool>(numCourses, false));
            // 构建图
            for (vector<int>& p : prerequisites)
            {
                graph[p[0]][p[1]] = true;
            }
            for (int k = 0; k < numCourses; ++k)
                for (int i = 0; i < numCourses; ++i)
                    for (int j = 0; j < numCourses; ++j)
                        graph[i][j] = graph[i][j]||(graph[i][k] && graph[k][j]);

            // 遍历quries直接从graph得到结果
            int n = queries.size();
            vector<bool> res(n);
            for (int i = 0; i < n; ++i)
            {
                res[i] = graph[queries[i][0]][queries[i][1]];
            }
            return res;
        }
    };
}